#include <iostream>
using namespace std;
#include "bstree.hpp"
#include<string>

namespace zq {
// 模板类要显示的示例化

template class BSTree<int,int>;
template class BSTree<int,char>;
template class BSTree<int,string>;
template class BSTree<string,string>;
template class BSTree_Node<string,string>;
template class BSTree<string,int>;


template <class K,class V> bool BSTree<K,V>::insert(const K &k,const V& v) {
  // 如果为空，就先插入一个
  if (_root == nullptr) {
    _root = new Node(k,v);
    return true;
  }
  // 开始遍历
  // 二叉搜索树是没有重复的值的
  Node *cur = _root;
  Node *parent = nullptr; // 前后指针法来实现链表的相连
  while (cur != nullptr) {
    if (cur->_key < k) {
      parent = cur;
      cur = cur->_right;
    } else if (cur->_key > k) {
      parent = cur;
      cur = cur->_left;
    } else {
      return false;
    }
  }

  // 到这里说明找到了要插入的位置
  // 开始插入
  cur = new Node(k,v);
  if (parent->_key < k) {
    parent->_right = cur;
  } else {
    parent->_left = cur;
  }
  return true;
}

//通过找key
template <class K,class V> 
BSTree_Node<K,V> * BSTree<K,V>::find(const K& k) {
  Node *cur = _root;
  while (cur != nullptr) {
    if (cur->_key < k) {
      cur = cur->_right;
    } else if (cur->_key > k) {
      cur = cur->_left;
    } else {
      return cur;
    }
  }
  return nullptr;
}
template <class K,class V> 
 void BSTree<K,V>::_InOrder(Node *root) {
  if (root == nullptr) {
    return;
  }
  // 递归中序遍历
  _InOrder(root->_left);
  cout << root->_key << " : "<<root->_value<<endl;
  _InOrder(root->_right);
}

template <class K,class V>  void BSTree<K,V>::InOrder() {
  _InOrder(_root);
  cout << endl;
}

// 删除逻辑的实现
template <class K,class V>  bool BSTree<K,V>::erase(const K &k) {
  Node *cur = _root;
  Node *parent = nullptr;
  while (cur) {
    if (cur->_key < k) {
      parent = cur;
      cur = cur->_right;
    } else if (cur->_key > k) {
      parent = cur;
      cur = cur->_left;
    } else {
      // 找到了，开始删除
      // 1：要删除的节点左孩子为空
      // 2：要删除的节点右孩子为空
      // 3：要删除的节点左右都不为空
      if (cur->_left == nullptr) {
        //左右孩子要处理为根的情况
        if (cur == _root) {
          _root = cur->_right;
        } else {
          if (parent->_left == cur) {
            parent->_left = cur->_right;
          } else {
            parent->_right = cur->_right;
          }
        }
        delete cur;
        return true;
      } else if (cur->_right == nullptr) {
        if (cur == _root) {
          _root = cur->_left;
        } else {
          if (parent->_left == cur) {
            parent->_left = cur->_left;
          } else {
            parent->_right = cur->_left;
          }
        }
        delete cur;
        return true;

      } else {
        // 删除的节点左右都不为空
        // 替换法
        // 1：去找左子树的最右节点
        // 2：去找右子树的最左节点
        Node *rightMinParent = cur;
        Node *rightMin = cur->_right; // 去找右边最左的节点
        while (rightMin->_left) {
          rightMinParent = rightMin;
          rightMin = rightMin->_left;
        }

        // 到这里就找到了
        cur->_key = rightMin->_key;
        // 转换成删除rightMin
        if (rightMin == rightMinParent->_left) {

          rightMinParent->_left = rightMin->_right;
        } else {

          rightMinParent->_right = rightMin->_right;
        }
        delete rightMin;
        return true;
      }
    }
  }
  return false;
}

} // namespace zq
